#include "prim.h"


Prim::Prim(const int& node_number)
	:res(0.)
{
	distance.resize(node_number, 0);			// 每一步之间的最大距离（第一步为起点，所以为0）
	is_traversa.resize(node_number, false);		// 第i个元素代表该索引下的节点是否被遍历
}

double Prim::calculate_max_spanning_tree(const vector<vector<double>>& matrix)
{
	is_traversa[0] = true;						// 将第一个节点设置为开始节点
	branch_node.push_back(0);					// 第一个节点为序号为0的节点
	for (int i = 1; i < distance.size(); i++)
	{
		// 记录与第一个节点相连的每个节点的距离
		distance[i] = std::max(distance[i], matrix[0][i]);	
	}

	for (int i = 1; i < distance.size(); i++)
	{
		double temp = 0.;						// 存放临时的最大距离
		int index = -1;							// 记录下一个点的下标
		for (int j = 1; j < distance.size(); j++)
		{
			// 节点是否被遍历且距离是否大于temp
			if (!is_traversa[j] && distance[j] > temp)
			{
				temp = distance[j];
				index = j;
			}
		}
		if (index == -1){res = -1.;return res;}	// index == -1代表构建失败
		is_traversa[index] = true;				// 节点被遍历后，将其设置为true
		res += distance[index];					// 计算当前的最大生成树距离
		branch_node.push_back(index);
		for (int j = 1; j < distance.size(); j++)
		{
			//用新加入的点更新distance
			if (!is_traversa[j])
			{
				distance[j] = std::max(distance[j], matrix[index][j]);
			}
		}
	}

	return res;
}